package com.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 131. 分割回文串
 * 回溯
 *
 * @author fy
 * @date 2022/4/27 19:06
 */
public class Solution131 {

    private List<List<String>> res;

    public List<List<String>> partition(String s) {
        res = new ArrayList<>();
        dfs(s, 0, new ArrayList<>());
        return res;
    }

    /**
     * 从字符串start位置开始到结尾搜索回文字符串
     *
     * @param s
     * @param start
     * @param preList 前面已经搜索到的回文字符串列表
     */
    private void dfs(String s, int start, List<String> preList) {
        if (start == s.length()) {
            // 这里必须要重新new一个list, 不然只使用引用会导致里面元素丢失
            res.add(new ArrayList<>(preList));
            return;
        }
        for (int i = start + 1; i <= s.length(); i++) {
            String subStr = s.substring(start, i);
            if (isPalindrome(subStr)) {
                // 如果当前切割的字符串是回文串, 则将字符串加入然后再次递归查找后续回文串
                preList.add(preList.size(), subStr);
                dfs(s, i, preList);
                // 递归结束需要将当前串移除
                preList.remove(preList.size() - 1);
            }
        }
    }

    private boolean isPalindrome(String subStr) {
        // 这段代码可以删掉如果subStr长度为1的话不会进while, 直接return true
        //if (subStr == null || subStr.length() == 1) {
        //    return true;
        //}
        int p = 0;
        int q = subStr.length() - 1;
        while (p < q) {
            if (subStr.charAt(p) != subStr.charAt(q)) {
                return false;
            }
            p++;
            q--;
        }
        return true;
    }


    public static void main(String[] args) {
        String s = "aabbcsddsedcsq";
        List<List<String>> res = new Solution131().partition(s);
        System.out.println(res);
    }

}
